package problems.contest;

import java.util.*;

/**
 * 2023力扣杯春季编程大赛
 *
 * @author dubulingbo, 2023-04-22, 022 14:59.
 */
public class SpringContest2023 {
    /**
     * T1.补给马车
     * <p>https://leetcode.cn/problems/hqCnmP/</p>
     */
    public int[] supplyWagon(int[] supplies) {
        int n = supplies.length;
        int newLen = n / 2;
        for (int i = n; i > newLen; --i) {

            int k = 0;
            int mv = Integer.MAX_VALUE;
            for (int j = 0; j < i - 1; ++j) {
                if (supplies[j] + supplies[j + 1] < mv) {
                    mv = supplies[j] + supplies[j + 1];
                    k = j;
                }
            }

            supplies[k] += supplies[k + 1];

            for (int j = k + 1; j < i - 1; ++j) {
                supplies[j] = supplies[j + 1];
            }
        }

        int[] ans = new int[newLen];

        System.arraycopy(supplies, 0, ans, 0, newLen);

        return ans;
    }


    /**
     * T2. 探险营地
     * <p>https://leetcode.cn/problems/0Zeoeg/</p>
     */
    public int adventureCamp(String[] es) {

        String[] ss = es[0].split("->");

        Set<String> old = new HashSet<>(Arrays.asList(ss));

        int cnt = 0;
        int idx = -1;
        for (int i = 1; i < es.length; ++i) {
            if (es[i] == null || es[i].equals("")) continue;
            ss = es[i].split("->");

            int c = 0;
            for (String s : ss) {
                if (!old.contains(s)) {
                    old.add(s);
                    ++c;
                }
            }

            if (c > cnt) {
                cnt = c;
                idx = i;
            }
        }
        return idx;
    }

    /**
     * T3. 最强祝福力场
     * <p>https://leetcode.cn/problems/xepqZ5/</p>
     */
    public int fieldOfGreatestBlessing1(int[][] forceField) {
        // 1. 坐标点离散化
        // 有序集合：唯一 + 有序
        Set<Long> xs = new TreeSet<>();
        Set<Long> ys = new TreeSet<>();

        for (int[] fo : forceField) {
            // x - side / 2：
            // 考虑到可能为小数，故将坐标转成整数：2 * x - side

            // 左上角坐标
            long x = 2L * fo[0] - fo[2];
            long y = 2L * fo[1] - fo[2];
            xs.add(x);
            ys.add(y);

            // 右下角坐标
            x = 2L * fo[0] + fo[2];
            y = 2L * fo[1] + fo[2];
            xs.add(x);
            ys.add(y);
        }
        int xn = xs.size();
        int yn = ys.size();
        long[] xAxis = new long[xn];
        long[] yAxis = new long[yn];
        int k = 0;
        for (long x : xs) xAxis[k++] = x;
        k = 0;
        for (long y : ys) yAxis[k++] = y;

        // 2. 二维差分
        int[][] m = new int[xn][yn];
        for (int[] f : forceField) {
            long lx = 2L * f[0] - f[2];
            long rx = 2L * f[0] + f[2];
            long ty = 2L * f[1] - f[2];
            long by = 2L * f[1] + f[2];
            // 通过二分找到当前坐标的离散化后的下标
            int lxi = Arrays.binarySearch(xAxis, lx);
            int rxi = Arrays.binarySearch(xAxis, rx);
            int tyi = Arrays.binarySearch(yAxis, ty);
            int byi = Arrays.binarySearch(yAxis, by);

            if (lxi >= 0 && tyi >= 0 && rxi >= 0 && byi >= 0) {
                // 左上 +1
                ++m[lxi][tyi];
                // 左下 -1
                if (byi + 1 < yn) --m[lxi][byi + 1];
                // 右上 -1
                if (rxi + 1 < xn) --m[rxi + 1][tyi];
                // 右下 +1
                if (byi + 1 < yn && rxi + 1 < xn) ++m[rxi + 1][byi + 1];
            }
        }

        // 二维前缀和计算答案
        int max = 0;
        for (int i = 0; i < xn; ++i) {
            for (int j = 0; j < yn; ++j) {
                if (j > 0) m[i][j] += m[i][j - 1];
                if (i > 0) m[i][j] += m[i - 1][j];
                if (i > 0 && j > 0) m[i][j] -= m[i - 1][j - 1];
                max = Math.max(m[i][j], max);
            }
        }

        return max;
    }

    public int fieldOfGreatestBlessing(int[][] forceField) {
        // 1. 坐标点离散化
        // 有序集合：唯一 + 有序
        Set<Long> xs = new TreeSet<>();
        Set<Long> ys = new TreeSet<>();

        for (int[] fo : forceField) {
            // x - side / 2：
            // 考虑到可能为小数，故将坐标转成整数：2 * x - side

            // 左上角坐标
            long x = 2L * fo[0] - fo[2];
            long y = 2L * fo[1] - fo[2];
            xs.add(x);
            ys.add(y);

            // 右下角坐标
            x = 2L * fo[0] + fo[2];
            y = 2L * fo[1] + fo[2];
            xs.add(x);
            ys.add(y);
        }
        int xn = xs.size();
        int yn = ys.size();
        long[] xAxis = new long[xn];
        long[] yAxis = new long[yn];
        int k = 0;
        for (long x : xs) xAxis[k++] = x;
        k = 0;
        for (long y : ys) yAxis[k++] = y;

        // 2. 二维差分
        // 前后预留 1 个位置，便于处理
        int[][] m = new int[xn + 2][yn + 2];
        for (int[] f : forceField) {
            long lx = 2L * f[0] - f[2];
            long rx = 2L * f[0] + f[2];
            long ty = 2L * f[1] - f[2];
            long by = 2L * f[1] + f[2];
            // 通过二分找到当前坐标的离散化后的下标
            // 改成下边从 1 开始
            int lxi = Arrays.binarySearch(xAxis, lx) + 1;
            int rxi = Arrays.binarySearch(xAxis, rx) + 1;
            int tyi = Arrays.binarySearch(yAxis, ty) + 1;
            int byi = Arrays.binarySearch(yAxis, by) + 1;

            // 左上 +1
            ++m[lxi][tyi];
            // 左下 -1
            --m[lxi][byi + 1];
            // 右上 -1
            --m[rxi + 1][tyi];
            // 右下 +1
            ++m[rxi + 1][byi + 1];
        }

        // 二维前缀和计算答案
        int ret = 0;
        for (int i = 1; i <= xn; ++i) {
            for (int j = 1; j <= yn; ++j) {
                // 自己 + 正上方 + 正左边 - 左上方
                m[i][j] += (m[i][j - 1] + m[i - 1][j] - m[i - 1][j - 1]);
                ret = Math.max(m[i][j], ret);
            }
        }

        return ret;
    }


    /**
     * T4|LCP 75. 传送卷轴
     * <p>https://leetcode.cn/problems/rdmXM7/</p>
     */
    final int[] dx = new int[] {0, 0, -1, 1};
    final int[] dy = new int[] {1, -1, 0, 0};
    char[][] mat;
    public int challengeOfTheKeeper(String[] maze) {
        /**
         * 1. 找到【初始位置】和【魔法水晶】位置
         * 2. bfs 计算【魔法水晶】位置到每个可达点的最短距离 dis[i][j]
         * 3. 二分答案
         */
        int n = maze.length;
        mat = new char[n][];
        // 【初始位置】的坐标
        int startX = -1, startY = -1;
        // 【魔法水晶】的位置坐标
        int endX = -1, endY = -1;
        for (int i = 0; i < n; ++i) {
            mat[i] = maze[i].toCharArray();
            if (startX + startY < 0 || endX + endY < 0) {
                for (int j = 0; j < n; ++j) {
                    if (mat[i][j] == 'S') {
                        startX = j;
                        startY = i;
                    } else if (mat[i][j] == 'T') {
                        endX = j;
                        endY = i;
                    }
                }
            }
        }

        // 2. 计算【魔法水晶】到各个点的最短距离
        int[][] dis = new int[n][n];
        Queue<int[]> que = new ArrayDeque<>();

        for (int i = 0; i < n; ++i) Arrays.fill(dis[i], Integer.MAX_VALUE);
        que.offer(new int[]{endX, endY});
        dis[endY][endX] = 0;

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                int[] cur = que.poll();
                int curX = cur[0];
                int curY = cur[1];
                for (int j = 0; j < dx.length; ++j) {
                    int nxtX = curX + dx[j];
                    int nxtY = curY + dy[j];
                    if (0 <= nxtX && nxtX < n && 0 <= nxtY && nxtY < n
                            // 不是墙壁
                            && mat[nxtY][nxtX] != '#'
                            // 还未访问过
                            && dis[nxtY][nxtX] == Integer.MAX_VALUE) {
                        que.offer(new int[] {nxtX, nxtY});
                        dis[nxtY][nxtX] = dis[curY][curX] + 1;
                    }
                }
            }
        }

        // 初始位置本身就无法达到【魔法水晶】
        if (dis[startY][startX] == Integer.MAX_VALUE) return -1;

        // 3. 二分枚举答案
        int l = -1, r = n * n + 1;
        int [][] vis = new int[n][n];
        while (l + 1 < r) {
            int step = (l + r) / 2;
            if (dfs(startX, startY, step, vis, dis)) r = step;
            else l = step;
        }

        return r > n * n ? -1 : r;
    }

    // 判断是否能在 maxStep 步数内能否到达【魔法水晶】
    private boolean dfs(int x, int y, int maxStep, int[][] vis, int[][] dis) {
        int n = mat.length;
        if (x < 0 || x >= n || y < 0 || y >= n // 越界
                || mat[y][x] == '#' // 走到墙壁
                || vis[y][x] == maxStep + 1) // 没有走过
            return false;
        // 到达终点
        if (mat[y][x] == 'T') return true;

        vis[y][x] = maxStep + 1;

        // 守护者使用卷轴，如果无法在 maxDis 内到达，则返回 false
        if (mat[y][x] == '.'
                && (mat[y][n - 1 - x] != '#' && dis[y][n - 1 - x] > maxStep
                || mat[n - 1 - y][x] != '#' && dis[n - 1 - y][x] > maxStep))
            return false;

        for (int i = 0; i < dx.length; ++i) {
            if (dfs(x + dx[i], y + dy[i], maxStep, vis, dis))
                return true;
        }

        return false;
    }


    public static void main(String[] args) {
//        SpringContest2023 test = new SpringContest2023();
//        System.out.println(test.adventureCamp(new String[]{"Alice->Dex", "", "Dex"}));
//        System.out.println(test.adventureCamp(new String[]{"xO->xO->xO", "xO->BKbWDH", "xO->BKbWDH", "BKbWDH->mWXW", "LSAYWW->LSAYWW", "oAibBvPdJ", "LSAYWW->u", "LSAYWW->LSAYWW"}));
        System.out.println(Integer.MAX_VALUE);

        Set<Long> set = new TreeSet<>();
        set.add(123L);
        set.add(2L);
        set.add(50L);
        set.add(500L);
        set.add(23123131L);
        set.add(1L);

        for (long v : set) {
            System.out.println(v);
        }
    }
}
